package utils

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func SortedArrayToBST(nums []int) *TreeNode {
	// 递归求解，中序遍历，反推Node
	numLen := len(nums)
	if numLen == 0 {
		return nil
	}

	mid := numLen / 2
	rootNode := &TreeNode{
		Val: nums[mid],
	}

	rootNode.Left = SortedArrayToBST(nums[0:mid])
	rootNode.Right = SortedArrayToBST(nums[mid+1:])

	return rootNode
}

func SortedArrayToPre(nums []int) *TreeNode {
	// 递归求解，先序遍历，反推Node
	numLen := len(nums)
	if numLen == 0 {
		return nil
	}

	rootNode := &TreeNode{
		Val: nums[0],
	}

	if numLen == 1 {
		return rootNode
	}
	mid := (numLen - 1) / 2

	rootNode.Left = SortedArrayToPre(nums[1 : mid+1])
	rootNode.Right = SortedArrayToPre(nums[mid+1:])

	return rootNode
}

func PrintTreeNode(root *TreeNode) {
	nodeQueue := []*TreeNode{
		root,
	}

	for len(nodeQueue) > 0 {
		queueLen := len(nodeQueue)

		for i := 0; i < queueLen; i++ {
			node := nodeQueue[i]
			if node.Left != nil {
				nodeQueue = append(nodeQueue, node.Left)
			}
			if node.Right != nil {
				nodeQueue = append(nodeQueue, node.Right)
			}
			print(node.Val, " -- ")
		}
		nodeQueue = nodeQueue[queueLen:]
		println()
	}
}
